package algorithm;

public class leetcode_0115 {
    public int numDistinct(String s, String t) {
        int lens=s.length();
        int lent=t.length();
        char[] lists=s.toCharArray();
        char[] listt=t.toCharArray();
        int [][] dp=new int[lent+1][lens+1];
        for(int j=0;j<=lens;++j){
            dp[0][j]=1;
        }
        for(int i=1;i<=lent;++i){
            for(int j=1;j<=lens;++j){
                if(lists[j-1]==listt[i-1]){
                    dp[i][j]=dp[i-1][j-1]+dp[i][j-1];
                }
                else{
                    dp[i][j]=dp[i][j-1];
                }
            }
        }
        return dp[lent][lens];
    }
}
